package main


/*
nums := []int{1, 4, 3, 7, 4, 5}
k = 3

k 代表指定位置的索引。这里k代表第3号元素 7。
求maxScore， score的定义是，求k位置向左，或向右，或者左右延伸。
包含的元素子集内，最小的元素 乘 元素个数 = score。求出所有 score中最大的。

上面的例子maxScore是15.
解释：子集 [4, 3, 7, 4, 5] 也就是向左右分别延伸两个位置，
其中最小值是 3， 长度为5，所以 score = 3 x 5 = 15 是最大的score


解法分析， 我们先求出每步对应的最小值。因为往左往右计算， 都是要取集合中的最小值
7左边的依次是[1, 3, 3 7]
7右边的依次是[7, 4, 4]

可以发现规律， 7左边右边得出来的，一定是单调递减的！
整体的最小值数组为  [1, 3, 3, 7, 4, 4]。 是一个山脉数组。7最大，两边依次递减

那么问题转化为了双指针求解。初始位置指针都在7元素其所在位置，该移动谁呢？
参照 盛水最多容器那道题。  i - 1 与 j + 1 谁位置大，移动谁，因为最终计算结果大。
依次求出所有 score，  计算出最大的即可！
*/

import (
	"fmt"
)


func getMaxScore(nums []int, k int) int {
	// 1. 求出最小值数组, k左边
	minArr := make([]int, len(nums))
	minArr[k] = nums[k]
	minNum1 := nums[k]
	for i := k - 1; i >= 0; i-- {
		if nums[i] > minNum1 {
			minArr[i] = minNum1
		} else {
			minArr[i] = nums[i]
			minNum1 = nums[i]
		}
	}
	// k 右边
	minNum2 := nums[k]
	for i := k + 1; i < len(nums); i++ {
		if nums[i] > minNum2 {
			minArr[i] = minNum2
		} else {
			minArr[i] = nums[i]
			minNum2 = nums[i]
		}
	}
	fmt.Println(minArr)
	// 2.双指针，求解
	maxScore := nums[k]
	// 终止条件是两边都走到头了，或运算
	for i, j := k, k; j != len(nums) - 1 || i != 0; {
		// 计算左右往哪边移动。
		// 左右都不出界的情况
		if i - 1 >= 0 && j + 1 < len(nums) {
			if minArr[i - 1] > minArr[j + 1] {
				i -= 1
			} else {
				j += 1
			}
		} else if i - 1 >= 0{  // 右边在边界，左边不出界
			i -= 1
		} else {  // 右边不出界的情况
			j += 1
		}
		// 4. 计算maxScore
		maxScore = max(maxScore, min(minArr[i], minArr[j]) * (j - i + 1))
	}
	// 5. 返回结果
	return maxScore
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}


func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	//a := 0
	//fmt.Scan(&a)
	//fmt.Printf("%d\n", a)
	nums := []int{1, 4, 3, 7, 4, 5}
	k := 3
	ans := getMaxScore(nums, k)
	fmt.Printf("%d", ans);
}